1. Field of the Invention
The present invention relates to an apparatus and program for generating arithmetic containing a pseudo-random number required in a cryptosystem.
2. Description of the Related Art
An electronic community is being realized with the development of information technology including the Electronic Signature Law, the IT Document Batch Processing Law, etc. which have come into effect since 2001, online shopping through electronic mail, Internet, etc.
One of the key technologies of the electronic community can be arithmetic containing a cryptographical technology. In the electronic community, since important contents such as electronic documents, etc. are communicated through a network, the security technology for avoiding tapping and falsification is required. The indispensable technology for the security technology is a cryptographical technology, and generating a random number is very important step in the cryptographical technology.
A random number is a value obtained either completely at random or according to a predetermined rule, and generating such a value is called random number generation. The random number generation is an indispensable element in the recent security technology as one of the important constituent technologies for supporting the PKI (public key infrastructure). A random number can be an intrinsic random number or a pseudo-random number.
An intrinsic random number is a random number string which is arrayed completely at random and has nocycle. It is very difficult to use it as cryptograph, and there is a problem of efficiency in storing and transferring a long random number string. A pseudo-random number is a sequence which is hardly discriminated from an intrinsic random number generated using a predetermined arithmetic equation, etc., and it is practically useful to use a pseudo-random number instead of an intrinsic random number.
In a system in which the above mentioned pseudo-random number is used in various application fields, the security of the pseudo-random number affects the security of the system, and the generation efficiency of the pseudo-random number affects the speed of the entire system. Therefore, a pseudo-random number requires security and generation efficiency. Generally, a conventional pseudo-random number generation system seems to be secure, but the security is not clearly defined for the system, and most of these systems have only passed some statistical tests. On the other hand, a “cryptographical pseudo-random number” is defined to pass any polynomial time statistical test. That is, a “cryptographical pseudo-random number generating method” refers to a pseudo-random number generating method whose security is mathematically proved. However, there are no unconditional “cryptographical pseudo-random number generating methods”, and a type of assumption in calculation amount logic (normally considered to be reasonable) is defined.
The following methods are known as typical security provable pseudo-random number generating methods. In the following methods, k indicates the number of bits of q or N, and is normally called a security parameter.
BBS: The i-th internal status is represented by si=(si-1)2 m o d N (N indicates the Blum number), and the i-th output is the low order bits O (log k) of si. The security refers to the difficulty of the problem of factoring into prime components of the Blum number N.
BM: The i-th internal status is represented by si=gsi-1 m o d q (q indicates a prime number), and the i-th output is the high order bits O (log k) of si. g indicates a generator. The security refers to the difficulty of the problem of discrete logarithm.
The conventional pseudo-random number generation system is generally quick in operation, but lacks mathematic grounds for security, and has therefore been uncertain in security. On the other hand, the conventional cryptographical pseudo-random number generating system (BBS system and BM system) has mathematical assurance in security, but has a problem in arithmetic speed.
In the BBS system, about log k bits can be output in one multiplication. In the BM system, about k multiplications are required for one arithmetic operation containing a power, and can output k−ω (log k) bits (ω indicates the order of a function truly larger than log k, and smaller than k). Assuming that k=approximately 1000 is selected as a realistic security parameter, about 10 bits can be output in one multiplication in the BBS system, and about one bit can be output in one multiplication in the BM system.